package com.lfg.leetcode.leetcode100;


import com.lfg.leetcode.leetcode0.ListNode;

public class No147insertionSortList {

    public static void main(String[] args) {
        ListNode ret = insertionSortList(ListNode.deserialize("[3,2,1,6,5,-1]"));
        System.out.println(ret);
    }

    public static ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode ret = head;
        ListNode node = head;

        while (node.next != null) {
            if (node.next.val >= node.val) {
                node = node.next;
                continue;
            }
            ListNode current = node.next;
            ListNode next = node.next.next;

            if (current.val < ret.val) {
                current.next = ret;
                ret = current;
                node.next = next;
                continue;
            }

            ListNode listNode = ret;
            while (listNode.next != null) {
                if (listNode.next.val > current.val) {
                    break;
                }
                listNode = listNode.next;
            }
            current.next = listNode.next;
            listNode.next = current;
            node.next = next;
        }
        node.next = null;
        return ret;
    }
}
